package com.zlk.algorithm.algorithm.sort.practice;

import com.zlk.algorithm.algorithm.sort.SortUtils;
import org.junit.Test;

import java.util.Arrays;

/**
 * @program: algorithm
 * @ClassName Index
 * @description:
 * @author: slfang
 * @create: 2024-11-21 15:15
 * @Version 1.0
 **/
public class Index {

    @Test
    public void test(){
        int testTimes = 10000;
        int randomLength = 20;
        int randomVal = 100;

        for (int i = 0; i < testTimes; i++) {
            int[] randomArr1 = SortUtils.getRandomArr(randomVal, randomLength);
            int[] copy = SortUtils.copyArray(randomArr1);
            SortUtils.comparator(copy);
            //bubbleSort(randomArr1);
            //selectionSort(randomArr1);
            //insertionSort(randomArr1);
            mergerSort(randomArr1);
            //heapSort(randomArr1);
            if(!SortUtils.isEqual(copy,randomArr1)){
                System.out.println("第"+(i+1)+"测试失败"+ Arrays.toString(copy));
                System.out.println("第"+(i+1)+"测试失败"+ Arrays.toString(randomArr1));
            }
        }
        System.out.println("success !!!");
    }


    public void bubbleSort(int[] arr){
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i <arr.length ; i++) {
            for (int j = 0; j <arr.length-i ; j++) {
                if(arr[j]>arr[j+1]){
                    SortUtils.swap(arr,j,j+1);
                }
            }
        }
    }

    public void selectionSort(int[] arr){
        if(arr==null||arr.length<=1){
            return ;
        }
        int size = arr.length;

        for (int i = 0; i < size; i++) {
            int min = i;
            for (int j = i+1; j < size; j++) {
                if(arr[j]<arr[min]){
                    min = j;
                }
            }
            if(min !=i){
                SortUtils.swap(arr,min,i);
            }
        }
    }


    public void insertionSort(int[] arr){
        if(arr==null||arr.length<=1){
            return ;
        }
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int temp = i;
            while (temp-1>=0&&arr[temp-1]>arr[temp]){
                SortUtils.swap(arr,temp-1,temp);
                temp--;
            }
        }
    }

    public void mergerSort(int[] arr){
        if(arr==null||arr.length<=1){
            return ;
        }
        int len = arr.length;
        mergerSort(arr,0,len-1);

    }

    private void mergerSort(int[] arr, int l, int r) {
        if(l>=r){
            return ;
        }
        int mid = l+(r-l)/2;
        mergerSort(arr,l,mid);
        mergerSort(arr,mid+1,r);
        merger(arr,l,r,mid);
    }

    private void merger(int[] arr, int l, int r,int mid) {
        int len = r-l+1;
        int[] temp = new int[len];
        int lIndex = l;
        int rIndex = mid+1;
        int index = 0;
        // 1  2 5 3  4
        // 0  1 2
        while (lIndex<=mid&&rIndex<=r){
            temp[index++] = arr[lIndex]<=arr[rIndex]?arr[lIndex++]:arr[rIndex++];
        }
        while (lIndex<=mid){
            temp[index++] =arr[lIndex++];
        }
        while (rIndex<=r){
            temp[index++] =arr[rIndex++];
        }

        for (int i = 0; i <len ; i++) {
            arr[l+i] = temp[i];
        }
    }






}
